/**
 * 优化为一维数组的方式。
 **/

#include <bits/stdc++.h>
using namespace std;
int dp[1002];
int W[102], V[102];
int T, M;
int main()
{
#ifdef LOCAL
    freopen("ALGO-30.in", "r", stdin);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T >> M;
    for(int i = 1; i <= M; ++i)
        cin >> W[i] >> V[i];
    for(int i = 1; i <= M; ++i) 
        for(int j = T; j >=1 ; --j) 
            if(W[i] <= j) dp[j] = max(dp[j], dp[j - W[i]] + V[i]);
    cout << dp[T] << endl;
    return 0;
}